﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     *      
     * Using all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be formed. 
     * Interestingly with the set {2,5,47,89,631}, all of the elements belonging to it are prime.
     * 
     * How many distinct sets containing each of the digits one through nine exactly once contain only prime elements?
     * */
    class Problem118 : IProblem
    {
        public string Calculate()
        {
            List<char> characters = new List<char>() { '1', '2', '3', '4', '5', '6', '7', '8', '9' };


            var q = CommonFunctions.GetPermutation(characters).Select(x => CountValid(x, new List<int>()));

            long sum = q.Sum();

            return sum.ToString();
        }

        SieveOfAtkin sieve = new SieveOfAtkin(1000000);

        HashSet<string> seen = new HashSet<string>();


        long CountValid(string number, List<int> used)
        {
            string temp = "";
            long count = 0;
            for (int i = number.Length - 1; i >= 0; i--)
            {
                temp = number.Substring(i);

                int n = int.Parse(temp);
                if (sieve.IsPrime(n))
                {
                    List<int> newUsed = new List<int>(used);
                    newUsed.Add(n);

                    if (i == 0)
                    {
                        newUsed = newUsed.OrderBy(x => x).ToList();

                        String set = newUsed[0] + "";
                        for (int j = 1; j < newUsed.Count; j++)
                            set += "," +newUsed[j] ;

                        if (seen.Contains(set))
                        {
                            return count;
                        }
                        else
                        {
                            seen.Add(set);
                            return count + 1;
                        }
                    }
                    else
                    {
                        count += CountValid(number.Substring(0, i), newUsed);
                    }
                }
            }
            return count;
        }
    }
}
